import java.util.HashMap;

public class l76_最小覆盖子串 {
    public static void main(String[] args) {


        System.out.println(minWindow("ADOBECODEBANC","ABC"));
    }
    public  static  String minWindow(String s, String t) {
        int left = 0;
        int right = 0;
        String tmpRes = "" ;
        int flag = t.length();
        //初始化map的值
        HashMap<Character,Integer> now = new HashMap<>();
        HashMap<Character,Integer> nowFinal = new HashMap<>();
        for (int i=0 ; i< t.length();i++){
            char c = t.charAt(i) ;
            if (now.containsKey(c)){
                now.put(c , now.get(c) + 1 );
                nowFinal.put(c , now.get(c) + 1 );
            }else {
                now.put(c,1);
                nowFinal.put(c,1);
            }
        }
        String tmpstr = "";
        while (left != s.length()){
            while (flag != 0 &&  right < s.length()){
                char tmpChar = s.charAt(right);
                if (now.containsKey(tmpChar) ){
                    if (now.get(tmpChar) > 0){
                        flag -= 1;
                    }
                    now.put(tmpChar,now.get(tmpChar)-1);
                    right += 1 ;
                }else {
                    right += 1 ;
                }
            }
            if (flag == 0){
                tmpstr = s.substring(left,right);
                int nowLeng = right - left;
                if (tmpRes.equals("") || tmpstr.length() < tmpRes.length())
                    tmpRes = tmpstr;
            }
            tmpstr = s.substring(left,right);
            char tmpCharLeft = s.charAt(left);
            if (now.containsKey(tmpCharLeft)){
                if (now.get(tmpCharLeft) < nowFinal.get(tmpCharLeft) && now.get(tmpCharLeft) >=0)
                    flag += 1 ;
                now.put(tmpCharLeft,now.get(tmpCharLeft)+1);
                left += 1;
            }else {
                left += 1;
            }
            tmpstr = s.substring(left,right);
        }

        return   tmpRes;




    }
}
